package com.heima.leetcode.practice;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 207. 课程表
 * @date 2025/1/26 10:04
 */
public class E207 {

    // 这道题可以转化为有向图有无环问题，然后用拓扑排序解题
    // 必须选修 numCourses 门课程，根据先修关系构造有向图，如果有循环依赖，则无法修完所有课程

    /**
     * 顶点
     */
    static class Vertex {

        /**
         * 课程编号
         */
        int courseNum;

        /**
         * 入度
         */
        int inDegree;

        /**
         * 课程状态，0表示该顶点未访问，1表示正在访问（处于递的周期里面），2表示访问完成（该顶点已完成归的操作）
         */
        int status;

        /**
         * 该课程的所有出度边
         */
        List<Edge> edges;

        /**
         * 构造顶点
         *
         * @param courseNum 课程编号
         */
        Vertex(int courseNum) {
            this.courseNum = courseNum;
            this.edges = new LinkedList<>();
        }
    }

    /**
     * 边，这里不用考虑边的权重
     */
    static class Edge {

        /**
         * 边所连的顶点
         */
        Vertex linked;

        /**
         * 构造边
         *
         * @param linked 边所连的顶点
         */
        Edge(Vertex linked) {
            this.linked = linked;
        }
    }

    /**
     * <h3>方法一：Kahn算法：入度法</h3>
     *
     * @param numCourses    课程总数，课程编号从0到numCourses-1
     * @param prerequisites 依赖关系，其中prerequisites[i] = [ai, bi]，表示如果要学习课程ai则必须先学习课程bi
     * @return 是否可以修完所有课程
     */
    public boolean canFinish1(int numCourses, int[][] prerequisites) {
        // 1. 构建有向图
        List<Vertex> vertices = new ArrayList<>();
        // 1.1 添加顶点
        for (int i = 0; i < numCourses; i++)
            vertices.add(new Vertex(i));
        // 1.2 添加边和设置入度
        for (int[] prerequisite : prerequisites) {
            vertices.get(prerequisite[1]).edges
                    .add(new Edge(vertices.get(prerequisite[0])));
            vertices.get(prerequisite[0]).inDegree++;
        }
        // 2. 准备队列和result集合，队列用来存储入度为0的顶点，result集合用来存储拓扑排序的结果
        LinkedList<Vertex> queue = new LinkedList<>();
        List<Vertex> result = new ArrayList<>();
        // 3. 遍历顶点集合，将入度为0的顶点先加入队列
        for (Vertex vertex : vertices)
            if (vertex.inDegree == 0)
                queue.offer(vertex);
        // 4. 依次取出队列中的顶点放入结果集合中，并遍历每个顶点的邻接顶点，将这些邻接顶点的入度减一，如果有邻接顶点的入度减为0了，那么将这些顶点加入队列中
        while (!queue.isEmpty()) {
            Vertex poll = queue.poll();
            result.add(poll);
            for (Edge edge : poll.edges) {
                edge.linked.inDegree--;
                if (edge.linked.inDegree == 0)
                    queue.offer(edge.linked);
            }
        }
        // 5. 判断结果集合的长度是否等于课程总数，如果相等，则说明可以修完所有课程，否则不可以修完所有课程（存在环）
        return result.size() == numCourses;
    }

    /**
     * <h3>方法二：深度优先搜索</h3>
     *
     * @param numCourses    课程总数，课程编号从0到numCourses-1
     * @param prerequisites 依赖关系，其中prerequisites[i] = [ai, bi]，表示如果要学习课程ai则必须先学习课程bi
     * @return 是否可以修完所有课程
     */
    public boolean canFinish2(int numCourses, int[][] prerequisites) {
        // 1. 构建有向图
        List<Vertex> vertices = new ArrayList<>();
        // 1.1 添加顶点
        for (int i = 0; i < numCourses; i++)
            vertices.add(new Vertex(i));

        // 1.2 添加边
        for (int[] prerequisite : prerequisites)
            vertices.get(prerequisite[1]).edges
                    .add(new Edge(vertices.get(prerequisite[0])));
        // 2. 遍历顶点集合，对每个顶点进行深度优先搜索，如果搜索过程中出现环，则返回false，否则返回true
        for (Vertex vertex : vertices) {
            try {
                dfs(vertex);
            } catch (IllegalArgumentException e) {
                return false;
            }
        }
        return true;
    }

    /**
     * 深度优先搜索
     *
     * @param vertex 顶点
     */
    private void dfs(Vertex vertex) {
        // 1. 设置顶点状态为正在访问，递的过程，想象箭头
        vertex.status = 1;
        // 2. 遍历顶点的邻接顶点
        for (Edge edge : vertex.edges) {
            Vertex linked = edge.linked;
            // 2.1 如果邻接顶点未访问，则递归深度优先搜索
            if (linked.status == 0) dfs(linked);
            // 2.2 如果邻接顶点正在访问，递的过程，想想箭头，则存在环，返回false
            else if (linked.status == 1) throw new IllegalArgumentException("存在环");
            // 2.3 如果邻接顶点访问完成，归的过程已完成，想想箭头，最后是两个箭头指向同一个顶点，不是环，continue
        }
        // 3. 设置顶点状态为访问完成，归的过程，想想箭头，返回true
        vertex.status = 2;
    }
}
